/*
 * =====================================================================================
 *
 *       Filename:  2.cpp
 *
 *    Description:  编程珠玑第二章
 *
 *        Version:  1.0
 *        Created:  2011-11-10 20:12:43
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <new>
#include <bitset>

#include <boost/program_options.hpp>
namespace po = boost::program_options;

const unsigned int _maxcnt = 0x00FFFFFF;

void bit_set(int &v, int k)
{
    assert(0 <= k && k <= 31);
    v |= (0x01 << k);
}

void bit_clr(int &v, int k)
{
    assert(0 <= k && k <= 31);
    v &= ~(0x01 << k);
}

int bit_test(int v, int k)
{
    assert(0 <= k && k <= 31);
    return (v & (0x01 << k));
}

void bit_array_set(char *A, int k)
{
    A[k >> 3] |= (0x01 << (k >> 3) % 8);
}

void bit_array_clr(char *A, int k)
{
    A[k >> 3] &= ~(0x01 << (k >> 3) % 8);
}

int bit_array_test(char *A, int k)
{
    return (A[k >> 3] & (0x01 << (k >> 3) % 8));
}

//问题A，利用文件求解，不占用内存
int find_first_of_miss(const std::string &name)
{
    int r = 0;

    std::string in_name = name;
    std::string one_name = "zero.txt";
    std::string zero_name = "one.txt";

    for (int k = 23; k >= 0; --k) {
        std::stringstream zero_ss;
        zero_ss << k << zero_name;
        std::stringstream one_ss;
        one_ss << k << one_name;
        std::ifstream in(in_name.c_str());
        std::ofstream zero_file(zero_ss.str().c_str());
        std::ofstream one_file(one_ss.str().c_str());

        int tmp = 0, one_cnt = 0, zero_cnt = 0;

        while (in >> tmp) {
            if (bit_test(tmp, k)) {
                one_file << tmp << std::endl;
                one_cnt++;
            } else {
                zero_file << tmp << std::endl;
                zero_cnt++;
            }
        }

        if (one_cnt <= zero_cnt) {
            in_name = one_ss.str();
            bit_set(r, k);
        } else {
            bit_clr(r, k);
            in_name = zero_ss.str();
        }
    }

    return r;
}

//问题A，解法二，利用位向量求解
int find_first_of_miss_use_bitset(const std::string &name)
{
    const int size = _maxcnt >> 8;
    char *A = NULL;

    try {
        A = new char[size + 1];
    } catch (std::bad_alloc &ba) {                //the class 'bad_alloc'
        std::cout << ba.what() << std::endl;
        exit(EXIT_FAILURE);
    }

    if (A == NULL) {
        std::cout << "not enough memory." << std::endl;
        return -1;
    }

    memset(A, 0, sizeof(char) * (size + 1));
    std::string in_name = name;

    unsigned int tmp = 0;
    std::ifstream in(in_name.c_str());

    while (in >> tmp) {
        std::cout << tmp << std::endl;

        if (!bit_array_test(A, tmp)) {
            bit_array_set(A, tmp);
        }
    }

    unsigned int miss = 0;

    for (unsigned int i = 0; i < _maxcnt; ++i) {
        if (!bit_array_test(A, i)) {
            miss = i;
            break;
        }
    }

    delete [] A;
    return miss;
}

int main(int argc, const char *argv[])
{
    // Declare the supported options.
    po::options_description desc("Allowed options");
    desc.add_options()
    ("help", "sort no duplcate inter value")
    ("file", po::value<std::string>(), "set the 2 billion count number file")
    ;

    po::variables_map vm;
    po::store(po::parse_command_line(argc, argv, desc), vm);
    po::notify(vm);

    if (vm.count("help")) {
        std::cout << desc << "\n";
        return 1;
    }

    if (vm.count("file")) {
        std::string name = vm["file"].as<std::string>();
        std::cout << "file was set to " << name << ".\n";

        clock_t start = clock();
        std::cout << "one miss number is " << find_first_of_miss_use_bitset(name) << std::endl;
        std::cout << "the running time of find_first_of_miss_use_bitset is " << (clock() - start) / CLOCKS_PER_SEC << std::endl;

        start = clock();
        std::cout << "one miss number is " << find_first_of_miss(name) << std::endl;
        std::cout << "the running time of find_first_of_miss is " << (clock() - start) / CLOCKS_PER_SEC << std::endl;
    } else {
        std::cout << "file was not set.\n";
    }

    return 0;
}
